package backTrack;

import normalArray.productExceptSelf;

public class exist {
    boolean flag = false;
    //上右下左
    int[] dirX = {-1,0,1,0};
    int[] dirY = {0,1,0,-1};
    public boolean exist(char[][] board, String word) {
        for(int i=0;i<board.length;i++){
            for(int j =0;j<board[0].length;j++){
                if (board[i][j]==word.charAt(0)) {
                    //找起点
                    boolean[][] mark = new boolean[board.length][board[0].length];
                    mark[i][j]=true;
                    backTrack(board, word, 0,i,j,mark);
                }
            }
        }
        return flag;

    }
    public void backTrack(char[][]board,String word,int pos,int row,int col,boolean[][]mark){
        if (pos==word.length()-1&&word.charAt(pos)==board[row][col]) {
            //成功了
            flag=flag|| true;
            return;
        }
        if (board[row][col]!=word.charAt(pos)) {
            return;
        }
        
        //遍历4个方向
        for(int i=0;i<4;i++){
            int x = dirX[i]+row;
            int y = dirY[i]+col;
            if (x<0||y<0||x>=board.length||y>=board[0].length||mark[x][y]) {
                continue;
            }else{
                mark[x][y]=true;
                backTrack(board,word,pos+1,x,y,mark);
                mark[x][y]=false;
            }
        }
    }
    public static void main(String[] args) {
        // char[][] board = new char[][] {
        // { 'A','B','C','E'},
        // {'S','F','C','S' },
        // { 'A','D','E','E' }
        // };
        char[][] board = new char[][] {
        { 'A','B','C'}
        
        };
        exist obj = new exist();
        System.out.println(obj.exist(board, "ABD"));
    }
}
